package algorithm.leetcode.I1to100;

/**
 * 非常强烈的DP题
 * 直接背答案
 * 设G(n)为长度为n的序列构成的不同的二叉搜索树的个数, F(i,n)以 i 为根、序列长度为 n 的不同二叉搜索树个数 (1≤i≤n)
 *
 * 1,2,...i-1,     i,    i+1,...,n
 *   G(i-1)     F(i,n)     G(n-i)
 *
 * 显然任意一个节点都可以作为根节点,于是F(i,n)的左子树可以是1到i-1的任意一个节点作为根节点,同理右子树可以是i+1到n的任意一个节点作为根节点
 * 所以 F(i,n) = G(i-1)*G(n-i)
 * G(n) = sigma i F(i,n) = sigma i G(i-1)*G(n-i), (1≤i≤n)
 */

public class Q96 {

    public int numTrees(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[i-j] * dp[j-1];
            }
        }
        return dp[n];
    }

}
